package sample.xiaosong.graphfunc;

import java.util.*;

/**
 * @author xiaosong
 */
public class GraphFunc {

    /**
     * 利用图的任一节点 开始广度优先遍历
     * @param node 图的任一节点
     */
    public static void BFS(GraphNode node) {
        if (node == null) {
            return;
        }
        // 利用队列实现广度优先遍历
        LinkedList<GraphNode> queue = new LinkedList<>();
        // 利用去重集合来避免循环
        HashSet<GraphNode> set = new HashSet<>();
        queue.add(node);
        set.add(node);
        while (!queue.isEmpty()) {
            node = queue.poll();
            System.out.println(node.value);
            for (GraphNode graphNode : node.next) {
                if (!set.contains(graphNode)) {
                    queue.add(graphNode);
                    set.add(graphNode);
                }
            }
        }
    }

    /**
     * 利用图的任一节点 开始深度优先遍历
     * @param node 图的任一节点
     */
    public static void DFS(GraphNode node) {
        if (node == null) {
            return;
        }
        // 利用栈实现深度优先遍历
        Stack<GraphNode> stack = new Stack<>();
        // 利用去重集合来避免循环
        HashSet<GraphNode> set = new HashSet<>();
        stack.add(node);
        set.add(node);
        System.out.println(node.value);
        while (!stack.isEmpty()) {
            node = stack.pop();
            for (GraphNode graphNode : node.next) {
                if (!set.contains(graphNode)) {
                    stack.push(node);
                    stack.push(graphNode);
                    set.add(graphNode);
                    System.out.println(graphNode.value);
                    break;
                }
            }
        }
    }

    /**
     * 拓扑排序算法   tips:经典场景，包的依赖问题
     * 要求：一个有入度为0的节点，且没有环的有向图
     * @param graph 图
     * @return 节点列表
     */
    public static List<GraphNode> sortedTopology(Graph graph) {
        // 入度map 记录每个节点的入度
        HashMap<GraphNode, Integer> inMap = new HashMap<>();
        // 所有入度为0 的节点 放入这个队列中
        Queue<GraphNode> inZeroQueue = new LinkedList<>();
        for (GraphNode node : graph.nodes.values()) {
            inMap.put(node, node.in);
            if (node.in == 0) {
                inZeroQueue.add(node);
            }
        }
        List<GraphNode> result = new ArrayList<>();
        while (!inZeroQueue.isEmpty()) {
            GraphNode cur = inZeroQueue.poll();
            result.add(cur);
            for (GraphNode node : cur.next) {
                inMap.put(node, inMap.get(node) - 1);
                if (inMap.get(node) == 0) {
                    inZeroQueue.add(node);
                }
            }
        }
        return result;
    }

    public static class GraphEdgeComparator implements Comparator<GraphEdge> {

        @Override
        public int compare(GraphEdge o1, GraphEdge o2) {
            return o1.weight - o2.weight;
        }

    }

    /**
     * 图的kruskal算法，目的为寻找最小生成树   K算法的出发角度为边
     * 要求图为  无向图
     * @param graph 图
     * @return 最小边的集合
     */
    public static Set<GraphEdge> kruskalMST(Graph graph) {
        //创建并查集结构体
        UnionFindSet unionFindSet = new UnionFindSet();
        // 初始化并查集
        unionFindSet.initSet(graph.nodes.values());
        // 创建边的小根堆
        PriorityQueue<GraphEdge> priorityQueue = new PriorityQueue<>(new GraphEdgeComparator());
        // 放入所有的边(由小到大)
        priorityQueue.addAll(graph.edges);
        Set<GraphEdge> result = new HashSet<>();
        // 一次取出所有的边
        while (!priorityQueue.isEmpty()) {
            GraphEdge graphEdge = priorityQueue.poll();
            GraphNode from = graphEdge.from;
            GraphNode to = graphEdge.to;
            // 如果边的两个节点不在同一集合，进行合并，并把这条边加入结果集
            if (!unionFindSet.isSameSet(from, to)) {
                unionFindSet.unionSet(from, to);
                result.add(graphEdge);
            }
        }
        return result;
    }

    /**
     * 图的prim算法，目的为寻找最小生成树   P算法的出发角度为点
     * 要求图为  无向图
     * @param graph 图
     * @return 最小边的集合
     */
    public static Set<GraphEdge> primMST(Graph graph) {
        // 创建边的小根堆
        PriorityQueue<GraphEdge> priorityQueue = new PriorityQueue<>(new GraphEdgeComparator());
        // 创建集合记录使用过的节点
        Set<GraphNode> set = new HashSet<>();
        Set<GraphEdge> result = new HashSet<>();
        // 循环取出所有节点
        for (GraphNode graphNode : graph.nodes.values()) {
            // 使用过的节点不再重复使用
            if (!set.contains(graphNode)) {
                // 当前节点加入集合
                set.add(graphNode);
                // 当前节点的所有边加入小根堆
                priorityQueue.addAll(graphNode.edges);
                // 循环取出所有的边
                while (!priorityQueue.isEmpty()) {
                    GraphEdge edge = priorityQueue.poll();
                    GraphNode toNode = edge.to;
                    // 边的to节点不在集合内，加入集合，并加入to节点的所有边到小根堆
                    // 将当前边加入结果集
                    if (!set.contains(toNode)) {
                        set.add(toNode);
                        priorityQueue.addAll(toNode.edges);
                        result.add(edge);
                    }
                }
            }
        }
        return result;
    }

    /**
     * 图的dijkstra算法，目的为寻找从头节点出发，到达每个节点的最短路径
     * 条件为：没有权值为负数的边
     * @param head 任一节点当头节点
     * @return 节点  和  头节点到该节点的路径权重
     */
    public static Map<GraphNode, Integer> dijkstra(GraphNode head) {
        // 记录每个节点 和 头节点到该节点的路径权重
        Map<GraphNode, Integer> distanceMap = new HashMap<>();
        // 头节点到自己的权重为 0
        distanceMap.put(head, 0);
        // 已经处理过得节点集合
        Set<GraphNode> selectedNodes = new HashSet<>();

        // 获取最小路径权重的节点
        GraphNode minNode = getMinDistanceAndUnselectedNode(distanceMap, selectedNodes);
        while (minNode != null) {
            // 取出这个节点的权重值(从头节点到该节点的累计值)
            int distance = distanceMap.get(minNode);
            // 循环节点的所有边
            for (GraphEdge edge : minNode.edges) {
                GraphNode toNode = edge.to;
                // 更新每条边的to节点，以及到该节点的权重值
                if (!distanceMap.containsKey(toNode)) {
                    distanceMap.put(toNode, distance + edge.weight);
                } else {
                    distanceMap.put(toNode, Math.min(distanceMap.get(toNode), distance + edge.weight));
                }
            }
            // 将处理过得最小节点放进集合
            selectedNodes.add(minNode);
            // 更新最小节点
            minNode = getMinDistanceAndUnselectedNode(distanceMap, selectedNodes);
        }
        return distanceMap;
    }

    /**
     * 从节点map中获取最小路径的节点
     * @param distanceMap 节点都后续节点map
     * @param selectedNodes 已经处理过的节点集合
     * @return 最小路径的节点
     */
    private static GraphNode getMinDistanceAndUnselectedNode(Map<GraphNode, Integer> distanceMap,
                                                             Set<GraphNode> selectedNodes) {
        // 初始化最小节点 和 最小权重
        GraphNode minNode = null;
        int minDistance = Integer.MAX_VALUE;
        // 循环找到未使用过的最小权重节点
        for (Map.Entry<GraphNode, Integer> entry : distanceMap.entrySet()) {
            GraphNode node = entry.getKey();
            int distance = entry.getValue();
            if (!selectedNodes.contains(node) && distance < minDistance) {
                minNode = node;
                minDistance = distance;
            }
        }
        return minNode;
    }

    /**
     * 图的dijkstra2算法，为前一个节点的优化版，主要使用了自己实现的小根堆
     * 条件为：没有权值为负数的边
     * @param head 任一节点当头节点
     * @return 节点  和  头节点到该节点的路径权重
     */
    public static Map<GraphNode, Integer> dijkstra2(GraphNode head, int size) {
        // 新建小根堆
        GraphNodeHeap nodeHeap = new GraphNodeHeap(size);
        // 初始化头节点
        nodeHeap.insertOrUpdateOrIgnore(head, 0);
        // 结果集
        Map<GraphNode, Integer> result = new HashMap<>();
        // 边界条件为小根堆全部弹出
        while (!nodeHeap.isEmpty()) {
            // 取出堆顶元素
            GraphNodeRecord record = nodeHeap.pop();
            GraphNode cur = record.graphNode;
            int distance = record.distance;
            // 循环堆顶元素的所有边，并将每条边的to节点加入小根堆
            for (GraphEdge edge : cur.edges) {
                nodeHeap.insertOrUpdateOrIgnore(edge.to, distance + edge.weight);
            }
            // 将堆顶元素加入结果集
            result.put(cur, distance);
        }
        return result;
    }

    public static class GraphNodeRecord {
        public GraphNode graphNode;
        public int distance;

        public GraphNodeRecord(GraphNode graphNode, int distance) {
            this.graphNode = graphNode;
            this.distance = distance;
        }
    }

    public static class GraphNodeHeap {
        public GraphNode[] nodes;
        public int size;
        public HashMap<GraphNode, Integer> distanceMap;
        public HashMap<GraphNode, Integer> indexMap;

        public GraphNodeHeap(int size) {
            nodes = new GraphNode[size];
            this.size = 0;
            distanceMap = new HashMap<>();
            indexMap = new HashMap<>();
        }

        public boolean isEmpty() {
            return size == 0;
        }

        /**
         * 新增 or 更新 or 忽略 节点
         * 对于第一次加入的节点 insert
         * 对于还在堆中的节点 update
         * 对于已经处理过的节点 ignore
         * @param node 节点
         * @param distance 权重
         */
        public void insertOrUpdateOrIgnore(GraphNode node, int distance) {
            if (inHeap(node)) {
                // 在堆中的元素  更新小的权重值
                distanceMap.put(node, Math.min(distance, distanceMap.get(node)));
                insertHeapify(indexMap.get(node));
            }
            // 不在堆中，且没有处理过的元素  新增
            if (!isEntered(node)) {
                nodes[size] = node;
                indexMap.put(node, size);
                distanceMap.put(node, distance);
                insertHeapify(size++);
            }
        }

        /**
         * 弹出堆顶元素
         * 将堆顶元素和最后一个元素交换
         * 然后删除最后一个元素
         * @return 堆顶元素记录
         */
        public GraphNodeRecord pop() {
            GraphNodeRecord record = new GraphNodeRecord(nodes[0], distanceMap.get(nodes[0]));
            swap(0, size - 1);
            distanceMap.remove(nodes[size - 1]);
            indexMap.put(nodes[size - 1], -1);
            nodes[size - 1] = null;
            heapify(0, --size);
            return record;
        }

        /**
         * 小根堆新增节点后自排序
         * 如果当前下标节点的distance值比父节点的distance值小，交换二者的位置
         * 将当前index下标变为父节点的下标
         * 一直循环下去，直到找到不比自己小的父节点
         * @param index 新增下标
         */
        private void insertHeapify(int index) {
            while (distanceMap.get(nodes[index]) < distanceMap.get(nodes[(index - 1) / 2])) {
                swap(index, (index - 1) / 2);
                index = (index - 1) / 2;
            }
        }

        /**
         * 小根堆弹出元素后的自调整
         *
         * 堆在弹出元素时，默认是弹出堆顶元素，即为数组的第一个元素
         * 首先 将一个元素和最后一个元素交换
         * 然后 将新的头节点和他左右子节点做对比，找到小的节点
         * 最后 将头节点和小的节点交换，直到找到自己的位置
         * @param index 元素位置 实际上永远是0
         * @param size 堆的大小
         */
        private void heapify(int index, int size) {
            // 获取左节点下标
            int left = index * 2 + 1;
            // 边界条件 左子节点下标达到堆的大小
            while (left < size) {
                // 判断右子节点下标是否超过size   如果没有，比较左右子节点的distance值，取最小的子节点index
                int smallest = left + 1 < size && distanceMap.get(nodes[left]) < distanceMap.get(nodes[left + 1])
                        ? left : left + 1;
                // 最小的子节点index 再和 参数index取小
                smallest = distanceMap.get(nodes[index]) < distanceMap.get(nodes[smallest]) ? index : smallest;
                // 最小的就是自己，直接跳出循环
                if (smallest == index) {
                    break;
                }
                // 交换二者位置，向下遍历
                swap(smallest, index);
                index = smallest;
                left = index * 2 + 1;
            }
        }

        // 判断节点是否加入过堆
        private boolean isEntered(GraphNode node) {
            return indexMap.containsKey(node);
        }

        // 判断节点现在是否还在堆中
        private boolean inHeap(GraphNode node) {
            return isEntered(node) && indexMap.get(node) != -1;
        }

        // 交换两个位置的元素
        private void swap(int index1, int index2) {
            indexMap.put(nodes[index1], index2);
            indexMap.put(nodes[index2], index1);
            GraphNode tempNode = nodes[index1];
            nodes[index1] = nodes[index2];
            nodes[index2] = tempNode;
        }
    }

    public static void main(String[] args) {
        GraphNode node1 = new GraphNode(1);
        GraphNode node2 = new GraphNode(2);
        GraphNode node3 = new GraphNode(3);
        GraphNode node4 = new GraphNode(4);
        GraphNode node5 = new GraphNode(5);
        GraphNode node6 = new GraphNode(6);
        GraphNode node7 = new GraphNode(7);
        GraphNode node8 = new GraphNode(8);
        node1.next.add(node2);
        node1.next.add(node6);
        node2.next.add(node1);
        node2.next.add(node3);
        node2.next.add(node5);
        node3.next.add(node2);
        node3.next.add(node4);
        node4.next.add(node5);
        node4.next.add(node6);
        node4.next.add(node7);
        node5.next.add(node2);
        node5.next.add(node4);
        node5.next.add(node6);
        node6.next.add(node1);
        node6.next.add(node5);
        node6.next.add(node4);
        node6.next.add(node8);
        node7.next.add(node4);
        node7.next.add(node8);
        node8.next.add(node6);
        node8.next.add(node7);

        System.out.println("========================BFS===========================");
        BFS(node1);

        System.out.println("========================DFS===========================");
        DFS(node1);

        /*
          一个有入度为0的节点，且没有环的有向图
           0(weight)    1(from)    2(to)
           ---------------------------------------------
        0 |    1          1          2
        1 |    2          1          3
        2 |    3          2          4
        3 |    4          3          4
        4 |    5          3          5
        5 |    6          4          6
        6 |    7          5          7
        7 |    8          6          7
         */
        Integer[][] matrix = new Integer[][] {{1, 1, 2}, {2, 1, 3}, {3, 2, 4}, {4, 3, 4}, {5, 3, 5}, {6, 4, 6},
                {7, 5, 7}, {8, 6, 7}};
        Graph graph = Graph.getInstance(matrix);
        System.out.println("========================sortedTopology===========================");
        List<GraphNode> result = sortedTopology(graph);
        for (GraphNode node : result) {
            System.out.println(node.value);
        }

        //无向图
        Integer[][] matrix2 = new Integer[][] {
                {1, 1, 2}, {2, 1, 3}, {3, 2, 4}, {4, 3, 4}, {5, 3, 5}, {6, 4, 6}, {7, 5, 7}, {8, 6, 7},
                {1, 2, 1}, {2, 3, 1}, {3, 4, 2}, {4, 4, 3}, {5, 5, 3}, {6, 6, 4}, {7, 7, 5}, {8, 7, 6}
        };
        Graph graph2 = Graph.getInstance(matrix2);
        System.out.println("========================kruskalMST===========================");
        Set<GraphEdge> graphEdgeSet = kruskalMST(graph2);
        for (GraphEdge edge : graphEdgeSet) {
            System.out.println(edge.weight);
        }

        Graph graph3 = Graph.getInstance(matrix2);
        System.out.println("========================primMST===========================");
        Set<GraphEdge> graphEdgeSet1 = primMST(graph3);
        for (GraphEdge edge : graphEdgeSet1) {
            System.out.println(edge.weight);
        }

        System.out.println("========================dijkstra===========================");
        GraphNode head = graph3.nodes.get(1);
        Map<GraphNode, Integer> graphNodeMap = dijkstra(head);
        graphNodeMap.forEach((k, v) -> {
            System.out.println("node:" + k.value + "  distance:" + v);
        });

        System.out.println("========================dijkstra2===========================");
        GraphNode head2 = graph3.nodes.get(1);
        Map<GraphNode, Integer> graphNodeMap2 = dijkstra2(head2, 32);
        graphNodeMap2.forEach((k, v) -> {
            System.out.println("node:" + k.value + "  distance:" + v);
        });
    }
}
